package com.shuzijun.leetcode.editor.cn;
public class HouseRobberIi{
    public static void main(String[] args) {
         Solution solution = new HouseRobberIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1] );

        int max1 = rob_dp(nums,1,n-1);
        int max2 = nums[0] + rob_dp(nums,2,n-2);
        return Math.max(max1,max2);
    }

        private int rob_dp(int[] nums, int p, int r) {
            int n = nums.length;

            int[][] dp = new int[n][2];
            dp[p][0] = 0;
            dp[p][1] = nums[p];
            for (int i = p+1; i <= r; i++) {
                dp[i][0] = Math.max(dp[i-1][0] , dp[i-1][1]);
                dp[i][1] = dp[i-1][0] + nums[i];
            }

            return Math.max(dp[r][0] , dp[r][1]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}